//==============================================================================
//
//               Copyright (C) 2005  Dick van Oudheusden
//  
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this program; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2006-07-22 13:28:58 $ $Revision: 1.2 $
//
//==============================================================================

#include <stdlib.h>
#include <math.h>

#include "ofc/DGraph.h"
#include "ofc/DText.h"
#include "ofc/DFile.h"

#include "DInc.h"
#include "DTest.h"


//-DataType--------------------------------------------------------------------

void DGraph_test(void)
{
  DGraphNode    *node1     = nil;
  DGraphNode    *node2     = nil;
  DGraphNode    *node3     = nil;
  DGraphNode    *node4     = nil;
  DGraphNode    *node5     = nil;
  DGraphNode    *node6     = nil;
  DGraphNode    *node7     = nil;
  DGraphNode    *node8     = nil;
  DGraphEdge    *edge1     = nil;
  DGraphEdge    *edge2     = nil;
  DGraphEdge    *edge3     = nil;
  DGraphEdge    *edge4     = nil;
  DGraphEdge    *edge7     = nil;
  DGraphEdge    *edge8     = nil;
  DGraph        *graph     = [DGraph new];
  DGraph        *copy      = nil;
  DFile         *output    = [DFile new];
  DList         *path      = nil;
  double         weight;  
  DText         *obj       = [DText new];
  DText         *obx       = [DText new];
  DListIterator *iter      = nil;
  
  STARTTEST();

  [obj set :"Edge"];
  [obx set :"Node"];
  
  // Test shortest paths
  node1 = [graph addNode :NULL :NULL :nil]; // default label, no attributes and object
  node2 = [graph addNode :NULL :NULL :obx];
  node3 = [graph addNode :NULL :NULL :nil];
  node4 = [graph addNode :NULL :NULL :nil];
  node5 = [graph addNode :NULL :NULL :nil];
  node6 = [graph addNode :NULL :NULL :nil];
  node7 = [graph addNode :NULL :NULL :nil];
  node8 = [graph addNode :NULL :NULL :nil];
  
  edge1 = [graph addEdge :NULL :NULL : 6.0 :nil :node1 :node2];
  edge2 = [graph addEdge :NULL :NULL : 1.0 :obj :node2 :node3];
          [graph addEdge :NULL :NULL :10.0 :nil :node3 :node8];
          [graph addEdge :NULL :NULL : 4.0 :nil :node1 :node4];
          [graph addEdge :NULL :NULL : 3.0 :nil :node3 :node4];
          [graph addEdge :NULL :NULL : 8.0 :nil :node4 :node5];
  edge7 = [graph addEdge :NULL :NULL : 3.0 :nil :node3 :node5];
  edge8 = [graph addEdge :NULL :NULL : 3.0 :nil :node2 :node5];
          [graph addEdge :NULL :NULL : 7.0 :nil :node5 :node8];
          [graph addEdge :NULL :NULL :16.0 :nil :node1 :node6];
          [graph addEdge :NULL :NULL : 3.0 :nil :node5 :node6];
          [graph addEdge :NULL :NULL : 1.0 :nil :node6 :node7];
          [graph addEdge :NULL :NULL : 5.0 :nil :node5 :node7];
          [graph addEdge :NULL :NULL : 1.0 :nil :node7 :node8];

  if ([output open :"test.dot" :"w"])
  {
    TEST([graph toDot :output]);
    
    [output close];
  }
  path = [graph shortestPath :&weight :node1 :node8]; 

  TEST([path length] == 6);
  TEST(weight == 14.0);  
  TEST([path get :0] == node1);
  TEST([path get :1] == node2);
  TEST([path get :2] == node5);
  TEST([path get :3] == node6);
  TEST([path get :4] == node7);
  TEST([path get :5] == node8);
  
  [path shallowFree];

  // shallow copy the graph
  copy = [graph shallowCopy];

  iter = [copy nodes];
  
  path = [copy shortestPath :&weight :[iter first] :[iter last]]; 

  TEST([path length] == 6);
  TEST(weight == 14.0);  
  
  TEST([iter first] != node1);
  TEST([[iter next] object] == obx); // shallow copy, stored object is a reference
  TEST([iter last ] != node8);
  
  [iter free];
  [copy shallowFree];

  // deep copy the graph
  copy = [graph copy];

  iter = [copy nodes];
  
  path = [copy shortestPath :&weight :[iter first] :[iter last]]; 

  TEST([path length] == 6);
  TEST(weight == 14.0);  
  
  TEST([iter first] != node1);
  TEST([[iter next] object] != obx);         // deep copy, stored object is a copy ..
  TEST([[[iter object] object] compare :obx] == 0);  // .. and identical
  TEST([iter last ] != node8);
  
  [iter free];
  [copy free];

  // reroute
  [graph reroute :edge8 :node4 :node6];

  path = [graph shortestPath :&weight :node1 :node8]; 
  
  TEST([path length] == 5);
  TEST(weight == 9.0);  
  TEST([path get :0] == node1);
  TEST([path get :1] == node4);
  TEST([path get :2] == node6);
  TEST([path get :3] == node7);
  TEST([path get :4] == node8);
  
  [path shallowFree];

  // weight change
  [edge8 weight :12.0];

  path = [graph shortestPath :&weight :node1 :node8]; 
  
  TEST([path length] == 7);
  TEST(weight == 15.0);        
  TEST([path get :0] == node1);
  TEST([path get :1] == node2);
  TEST([path get :2] == node3);
  TEST([path get :3] == node5);
  TEST([path get :4] == node6);
  TEST([path get :5] == node7);
  TEST([path get :6] == node8);
  
  [path shallowFree];

  // reverse
  [edge7 reverse];

  path = [graph shortestPath :&weight :node1 :node8]; 
  
  TEST([path length] == 4);
  TEST(weight == 17.0);        
  TEST([path get :0] == node1);
  TEST([path get :1] == node2);
  TEST([path get :2] == node3);
  TEST([path get :3] == node8);
  
  [path shallowFree];

  // remove edge
  TEST([graph removeEdge :edge2] == obj);

  path = [graph shortestPath :&weight :node1 :node8]; 
  
  TEST([path length] == 6);
  TEST(weight == 17.0);
  TEST([path get :0] == node1);
  TEST([path get :1] == node4);
  TEST([path get :2] == node5);
  TEST([path get :3] == node6);
  TEST([path get :4] == node7);
  TEST([path get :5] == node8);
  
  [path shallowFree];

  // Remove node
  [graph removeEdge :edge1]; // disconnect the node
  
  TEST([graph removeNode :node2] == obx);
  
  [graph free];


  // Test graph output
  graph = [DGraph new];

  [graph attributes :"rotate=90"];
  
  node1 = [graph addNode :"start" :"shape=diamond" :nil]; TEST(node1 != nil);
  node2 = [graph addNode :NULL :NULL :nil]; TEST(node2 != nil);
  node3 = [graph addNode :NULL :NULL :nil]; TEST(node3 != nil);
  node4 = [graph addNode :NULL :NULL :nil]; TEST(node4 != nil);
  
  edge1 = [graph addEdge :"edge" :"color=red,style=dashed" :1.0 :nil :node1 :node2]; TEST(edge1 != nil);
  edge2 = [graph addEdge :NULL   :"arrowhead=crow" :2.0 :nil :node1 :node3]; TEST(edge2 != nil);
  edge3 = [graph addEdge :"loop" :NULL :3.0 :nil :node2 :node2]; TEST(edge3 != nil);
  edge4 = [graph addEdge :NULL   :NULL :4.0 :nil :node3 :node1]; TEST(edge4 != nil);

  TEST([node1 ingoingDegree] == 1);
  TEST([node2 ingoingDegree] == 2);
  TEST([node3 ingoingDegree] == 1);
  TEST([node4 ingoingDegree] == 0);

  TEST([node1 outgoingDegree] == 2);
  TEST([node2 outgoingDegree] == 1);
  TEST([node3 outgoingDegree] == 1);
  TEST([node4 outgoingDegree] == 0);

  TEST([node1 degree] == 3);
  TEST([node2 degree] == 3);
  TEST([node3 degree] == 2);
  TEST([node4 degree] == 0);

  TEST(strcmp([node1 name], "n1") == 0);
  TEST(strcmp([node4 name], "n4") == 0);
  TEST(strcmp([edge1 name], "e1") == 0);
  TEST(strcmp([edge4 name], "e4") == 0);
  
  TEST(strcmp([node1 label], "start") == 0);
  TEST([node4 label] == NULL);
  
  TEST(strcmp([edge1 label], "edge") == 0);
  TEST([edge4 label] == NULL);
  
  TEST(strcmp([graph attributes], "rotate=90") == 0);
  
  TEST(strcmp([node1 attributes], "shape=diamond") == 0);
  TEST([node4 attributes] == NULL);
  
  TEST(strcmp([edge2 attributes], "arrowhead=crow") == 0);
  TEST([edge4 attributes] == NULL);
  
  TEST([edge1 weight] == 1.0);
  TEST([edge3 weight] == 3.0);
  
  TEST([node3 object] == nil);
  TEST([node3 object :obj] == nil);
  TEST([node3 object :nil] == obj);
  TEST([node3 object] == nil);
  
  TEST([edge3 object] == nil);
  TEST([edge3 object :obj] == nil);
  TEST([edge3 object :nil] == obj);
  TEST([edge3 object] == nil);
  
  TEST([graph hasNode :node1]);
  TEST([graph hasEdge :edge3]);
  
  // Generate graph with: dot -Tpng -o graph.png test2.dot
  if  ([output open :"test2.dot" :"w"])
  {
    TEST([graph toDot :output]);
    
    [output close];
  }

  path = [graph shortestPath :NULL :node1 :node2];
  TEST([path length] == 2);
  [path shallowFree];
  
  path = [graph shortestPath :NULL :node1 :node4]; // no path present
  TEST(path == nil);
  
  [output free];
  [graph  free];
  [obj    free];
  [obx    free];
  
  STOPTEST();
}

